Algorithme de Buchberger
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
L'algorithme de Buchberger est un algorithme permettant de calculer une base de Gröbner pour un idéal polynomial à partir d'un ensemble générateur de l'idéal et d'un ordre sur les monômes. Il a été publié par le mathématicien autrichien Bruno Buchberger en 1976cite-ref-1[1].
En pseudo-code, il peut être décrit comme suitcite-ref-2[2] :
Entrées : un système de polynômes
F
=
(
f
1
,
…
,
f
s
)
{\displaystyle F=(f_{1},\dots ,f_{s})}
;
un ordre monomial
Sortie : une base de Gröbner de
⟨
f
1
,
…
,
f
s
⟩
{\displaystyle \langle f_{1},\dots ,f_{s}\rangle }
G
←
F
{\displaystyle G\leftarrow F}
Répéter
G
′
←
G
{\displaystyle G'\leftarrow G}
Pour chaque paire
{
p
,
q
}
{\displaystyle \{p,q\}}
dans
G
′
{\displaystyle G'}
:
m
←
ppcm
(
MD
(
p
)
,
MD
(
q
)
)
{\displaystyle m\leftarrow \operatorname {ppcm} (\operatorname {MD} (p),\operatorname {MD} (q))}
S
←
m
TD
(
p
)
p
−
m
TD
(
q
)
q
{\displaystyle S\leftarrow {\frac {m}{\operatorname {TD} (p)}}p-{\frac {m}{\operatorname {TD} (q)}}q}
r
←
{\displaystyle r\leftarrow }
reste de
S
{\displaystyle S}
par
G
′
{\displaystyle G'}
Si
r
{\displaystyle r}
est différent de 0 alors
G
←
G
∪
{
r
}
{\displaystyle G\leftarrow G\cup \{r\}}
Jusqu'à ce que
G
=
G
′
{\displaystyle G=G'}
Renvoyer
G
{\displaystyle G}
Le polynôme S {\displaystyle S} dans l'algorithme est appelé S {\displaystyle S} -polynôme de p {\displaystyle p} et q {\displaystyle q} , parfois noté S ( p , q ) {\displaystyle S(p,q)} . Les fonctions MD et TD sont respectivement le « monôme dominant » et le « terme dominant » (produit du monôme dominant par son coefficient).
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Références
cite-note-11. ↑ buchberger1976bruno-buchberger1976(en) Bruno Buchberger, « Theoretical Basis for the Reduction of Polynomials to Canonical Forms », ACM SIGSAM Bulletin, vol. 10, no 3, août 1976, p. 19-29.
cite-note-22. ↑ coxlittleo-shea2007david-a-coxjohn-littledon-o-shea2007(en) David A. Cox, John Little et Don O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, New York, Springer-Verlag, 2007, 3e éd. (lire en ligne), p. 83 et 90.
Article connexe
• Portail de l'informatique théorique
• Portail de l’algèbre